package ArrayList;

import java.util.Arrays;

/**
 * @Classname JZ11
 * @Description TODO
 * @Date 2022/12/6 9:28
 * @Created by xjl
 */
public class JZ11旋转数组的最小值 {
    /**
     * @description 暴力的方法   时间是nlog(n)
     * @param: numbers
     * @date: 2022/12/6 9:30
     * @return: int
     * @author: xjl
     */
    public int minArray(int[] numbers) {
        Arrays.sort(numbers);
        return numbers[0];
    }

    /**
     * @description 出现了突然下降额数据 依据都是递增的特性。 如果都是递增的那就是第一个最小了
     * 时间是n
     * @param: numbers
     * @date: 2022/12/6 9:34
     * @return: int
     * @author: xjl
     */
    public int minArray1(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < numbers[i - 1]) {
                return numbers[i];
            }
        }
        return numbers[0];
    }
    /**
     * @description 利用的二分法的性质来实现的
     * 时间是log2(n)
      * @param: numbers
     * @date: 2022/12/6 9:45
     * @return: int
     * @author: xjl
    */
    public int minArray2(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }

}
